/*
 * @Author: liusheng
 * @Date: 2022-04-21 17:04:58
 * @LastEditors: liusheng
 * @LastEditTime: 2022-04-21 22:33:02
 * @Description: 剑指 Offer II 038. 每日温度
 * email:liusheng613@126.com
 * Copyright (c) 2022 by liusheng/liusheng, All Rights Reserved. 
 * 
 剑指 Offer II 038. 每日温度
请根据每日 气温 列表 temperatures ，重新生成一个列表，要求其对应位置的输出为：要想观测到更高的气温，
至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用 0 来代替。


示例 1:

输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]
示例 2:

输入: temperatures = [30,40,50,60]
输出: [1,1,1,0]
示例 3:

输入: temperatures = [30,60,90]
输出: [1,1,0]
 

提示：

1 <= temperatures.length <= 105
30 <= temperatures[i] <= 100
 

注意：本题与主站 739 题相同： https://leetcode-cn.com/problems/daily-temperatures/
 */

#include "header.h"

/*
Time:O(n^2) solution
out of time
*/
class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        int n = temperatures.size();
        vector<int> waitingDays(n);
        for (int i = n - 1; i >= 0; --i)
        {
            int waitDayNum = 0;
            int curTemp = temperatures[i];
            for (int j = i + 1; j < n; ++j)
            {
                if (temperatures[j] > curTemp)
                {
                    waitDayNum = j - i;
                    break;
                }
            }
            waitingDays[i] = waitDayNum;
        }

        return waitingDays;
    }
};

/*
Monotonic Stack
单调栈技巧总结
单调栈
单调栈实际上就是栈，只是限制要比普通的栈更严格而已了。要求是每次入栈的元素必须要有序
（如果新元素入栈不符合要求，则将之前的元素出栈，直到符合要求再入栈），使之形成单调递增/单调递减的一个栈。

单调递增栈：只有比栈顶小的才能入栈，否则就把栈顶出栈后，再入栈。出栈时可能会有一些计算。适用于求解
第一个大于该位置元素的数。单调递减栈：与单调递增栈相反。适用于求解第一个小于该位置元素的数。

如何判断
单调递增/递减栈是根据出栈后的顺序来决定的。例如，栈内顺序[1, 2, 6]，出栈后顺序[6, 2, 1]，这就是单调递减栈。

适用场景
单调栈一般用于解决 第一个大于 xxx 或者 第一个小于 xxx 这种题目。
*/
class Solution2 {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        int n = temperatures.size();
        vector<int> waitingDays(n,0);

        //Monotonic decreasing  stack
        //keep the temperature that hasn't find a high value then it
        stack<int> singleStack;

        for (int i = 0; i < n; ++i)
        {
            int curTemp = temperatures[i];
            //use single decrease stack,only small than 
            //the top can be push to stack,otherwise pop the front until the stack is empty,so the stack will keep in decreasing order
            while (!singleStack.empty() && curTemp > temperatures[singleStack.top()])
            {
                int previousIndex = singleStack.top();
                singleStack.pop();
                waitingDays[previousIndex] = i - previousIndex;
            }

            singleStack.push(i);
        }

        return waitingDays;
    }
};

/*
Approach 1: Monotonic Stack
Intuition

Let's look at a data structure known as a Monotonic Stack. A monotonic stack is simply a stack where the elements 
are always in sorted order. How does this help us? We can use a monotonic decreasing stack to hold temperatures.
 Monotonic decreasing means that the stack will always be sorted in descending order. Because the problem is 
 asking for the number of days, instead of storing the temperatures themselves, we should store the indices of 
 the days, and use temperatures[i] to find the temperature of the ith day.

Monotonic stacks are a good option when a problem involves comparing the size of numeric elements, with their 
order being relevant.

On each day, there are two possibilities. If the current day's temperature is not warmer than the temperature 
on the top of the stack, we can just push the current day onto the stack - since it is not as warm (equal or 
smaller), this will maintain the sorted property.

If the current day's temperature is warmer than the temperature on top of the stack, this is significant. 
It means that the current day is the first day with a warmer temperature than the day associated with the 
temperature on top of the stack. When we find a warmer temperature, the number of days is the difference 
between the current index and the index on the top of the stack. We can declare an answer array before 
iterating through the input and populate answer as we go along.

When we find a warmer temperature, we can't stop after checking only one element at the top. Using the 
example temperatures = [75, 71, 69, 72], once we arrive at the last day our stack looks like 
stack = [0, 1, 2]. For clarity, here's what the stack looks like with each temperature associated with the
 day: stack = [(0, 75), (1, 71), (2, 69)]. 72 (the current temperature) is greater than 69, but it is also 
 greater than 71. To make sure we don't miss any days, we should pop from the stack until the top of the 
 stack is no longer colder than the current temperature. Once that is the case, we can push the current day 
 onto the stack.

Algorithm

Initialize an array answer with the same length as temperatures and all values initially set to 0. Also, 
initialize a stack as an empty array.

Iterate through temperatures. At each index currDay:

If the stack is not empty, that means there are previous days for which we have not yet seen a warmer day. 
While the current temperature is warmer than the temperature of prevDay (the index of the day at the top of 
the stack):
Set answer[prevDay] equal to the number of days that have passed between prevDay and the current day, that is,
 answer[prevDay] = currDay - prevDay.
Push the current index currDay onto the stack.
Return answer.

Here's an example animation showing how this algorithm works. For clarity, temperatures of the days are included with the indices:

*/

/*
solution to be solve:https://leetcode.com/problems/next-greater-element-ii/

496. Next Greater Element I
Easy

2635

177

Add to List

Share
The next greater element of some element x in an array is the first greater element that is to the right of x in the same array.

You are given two distinct 0-indexed integer arrays nums1 and nums2, where nums1 is a subset of nums2.

For each 0 <= i < nums1.length, find the index j such that nums1[i] == nums2[j] and determine the next greater element of nums2[j] in nums2. If there is no next greater element, then the answer for this query is -1.

Return an array ans of length nums1.length such that ans[i] is the next greater element as described above.

 

Example 1:

Input: nums1 = [4,1,2], nums2 = [1,3,4,2]
Output: [-1,3,-1]
Explanation: The next greater element for each value of nums1 is as follows:
- 4 is underlined in nums2 = [1,3,4,2]. There is no next greater element, so the answer is -1.
- 1 is underlined in nums2 = [1,3,4,2]. The next greater element is 3.
- 2 is underlined in nums2 = [1,3,4,2]. There is no next greater element, so the answer is -1.
Example 2:

Input: nums1 = [2,4], nums2 = [1,2,3,4]
Output: [3,-1]
Explanation: The next greater element for each value of nums1 is as follows:
- 2 is underlined in nums2 = [1,2,3,4]. The next greater element is 3.
- 4 is underlined in nums2 = [1,2,3,4]. There is no next greater element, so the answer is -1.
 

Constraints:

1 <= nums1.length <= nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 104
All integers in nums1 and nums2 are unique.
All the integers of nums1 also appear in nums2.
*/

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        //1 <= n <= m <=1000
        int n = nums1.size();
        int m = nums2.size();
        vector<int> nGreaterEle(n,-1);
        
        //construct monototic decreasing stack to get the first element greate than current
        stack<int> monototicDecrSt;
        unordered_map<int,int> numGreater; // num-> first greateNum key/value 
        
        for (int i = 0; i < m; ++i)
        {
            while (!monototicDecrSt.empty() && nums2[i] > monototicDecrSt.top())
            {
                numGreater[monototicDecrSt.top()] = nums2[i];
                monototicDecrSt.pop();
            }
            
            monototicDecrSt.push(nums2[i]);
        }
        
        for (int i = 0; i < n; ++i)
        {
            if (numGreater.count(nums1[i]))
            {
                nGreaterEle[i] = numGreater[nums1[i]];
            }
        }
        return nGreaterEle;
    }
};
